// https://www.lintcode.com/problem/convert-binary-search-tree-to-doubly-linked-list/my-submissions?_from=ladder&&fromId=6

/**
  * Definition of Doubly-ListNode
 * class DoublyListNode {
 * public:
 *     int val;
 *     DoublyListNode *next, *prev;
 *     DoublyListNode(int val) {
 *         this->val = val;
 *         this->prev = this->next = NULL;
 *     }
 * } * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
// struct ResultStruct {
//      DoublyListNode *head, *tail; //指针还要初始化，还是用类好。在坐标题目里面用struct。
// };
class ResultStruct 
{
    public:
    DoublyListNode *head, *tail;
    ResultStruct()
    {
        this->head = this->tail = NULL;
    }
};

class Solution {
public:
    /**
     * @param root: The root of tree
     * @return: the head of doubly list node
     */
    // 法一：栈，中序遍历
    // DoublyListNode * bstToDoublyList(TreeNode * root) {
    //     stack<TreeNode *> s;
    //     DoublyListNode * dummy = new DoublyListNode(-1);
    //     DoublyListNode * curr = dummy;
    //     while (!s.empty() || root)
    //     {
    //         while (root)
    //         {
    //             s.push(root);
    //             root = root->left;
    //         }
    //         TreeNode* tmp = s.top();
    //         s.pop();
    //         DoublyListNode * node = new DoublyListNode(tmp->val);
    //         curr->next = node;
    //         node->prev = curr;
    //         curr = curr->next;
    //         root = tmp->right;
    //     }
    //     return dummy->next;
    // }
    
    // 法二：分治法，需要重新定义数据结构，同时返回首尾
    // ResultStruct* getList(TreeNode * root)
    // {
    //     if(!root) return NULL;
    //     DoublyListNode * node = new DoublyListNode(root->val);
    //     // ResultStruct * result;
    //     ResultStruct * result = new ResultStruct(); // 指针要初始化
    //     result->head = result->tail = node;
    //     if(root->left) 
    //     {
    //         ResultStruct * left_result = getList(root->left);
    //         left_result->tail->next = node; 
    //         node->prev = left_result->tail;
    //         result->head = left_result->head;
    //     }
    //     if(root->right) 
    //     {
    //         ResultStruct * right_result = getList(root->right);
    //          // node->next = right_result.head;
    //         node->next = right_result->head; //注意指针只能用->访问成员
    //         right_result->head->prev = node;
    //         result->tail = right_result->tail;
    //     }
    //     return result;
    // }
    // DoublyListNode * bstToDoublyList(TreeNode * root) {
    //     if (!root) return NULL;
    //     ResultStruct* result = getList(root);
    //     return result->head;
    // }
    
    // 法三：记住pre，next
    DoublyListNode* getList(TreeNode* root,
                                  DoublyListNode* prev,
                                  DoublyListNode* next) 
    {
        if (!root) return NULL;
        DoublyListNode * node = new DoublyListNode(root->val);
        if (!root->left)
        {
            node->prev = prev;
            if (prev) node->prev->next = node;
        }
        else getList(root->left, prev, node);
        if (!root->right)
        {
            node->next = next;
            if (next) node->next->prev = node;
        }
        else getList(root->right, node, next);
        return node;
    }
    
    DoublyListNode * bstToDoublyList(TreeNode * root)
    {
        if (!root) return NULL;
         DoublyListNode* node = getList(root, NULL, NULL);
         while (node->prev) node = node->prev;
         return node;
    }
    
    // 法四：左子树的最右节点连到右子树 <链表节点顺序不对,这个是前序遍历的顺序> 
    // https://www.lintcode.com/problem/binary_tree_to_linked_list/description
    // void getList(TreeNode* root)
    // {
    //     while (root)
    //     {
    //         if (root->left)
    //         {
    //             TreeNode* tmp = root->left;
    //             while (tmp->right)
    //             {
    //                 tmp=tmp->right;
    //             }
    //             tmp->right = root->right;
    //             root->right = root->left;
    //             root->left = NULL;
    //         }
    //         root = root->right;
    //     }
    // }
    // DoublyListNode * bstToDoublyList(TreeNode * root) {
    //     getList(root);
    //     DoublyListNode * dummy = new DoublyListNode(-1);
    //     DoublyListNode * tmp = dummy;
    //     while (root)
    //     {
    //         tmp->next = new DoublyListNode(root->val);
    //         tmp->next->prev = tmp;
    //         root = root->right;
    //         tmp = tmp->next;
    //     }
    //     return dummy->next;
    // }
};